'''
Created on Dec 14, 2011

@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
import sys

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

# TEST functions

def test_hack_RSA():
    print("Testing Wiener Attack")
    times = 5
    
    while(times>0):
        e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
        print("(e,n) is (", e, ", ", n, ")")
        print("d = ", d)
    
        hacked_d = hack_RSA(e, n)
    
        if d == hacked_d:
            print("Hack WORKED!")
        else:
            print("Hack FAILED")
        
        print("d = ", d, ", hacked_d = ", hacked_d)
        print("-------------------------")
        times -= 1

def do_hack_RSA(n, e):
    print("-------------------------")
    print("Start Wiener Attack")
    print("-------------------------")

    hacked_d = hack_RSA(e, n)
    print("hacked_d =")
    print(hacked_d)

    print("-------------------------")


if __name__ == "__main__":
    #test_is_perfect_square()
    #print("-------------------------")
    #test_hack_RSA()
    
    n = 0
    e = 0
    help_str = '''
使用示例:
    python3 RSAwienerHacker.py -n xxx -e xxx

-n      n值
-e      e值
'''
    # 处理参数
    args = sys.argv[1:]
    prop = ""
    for a in args:
        if a[0] == "-":
            if a == "-n":
                prop = "n"
            elif a == "-e":
                prop = "e"
            elif a == "-h":
                print(help_str)
                exit()
            else:
                prop = ""
        else:
            if prop == "n":
                n = 0
            elif prop == "e":
                e = 0

    if n == 0:
        print('未指定n值')
        exit()
    if e == 0:
        print('未指定e值')
        exit()

    do_hack_RSA(n, e)


    


        
    
